package Offer083;

import java.util.*;

public class Test {
    public static void main(String[] args) {

    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length == 0) {
            return list;
        }
        Deque<Integer> path = new LinkedList<>();
        int len = nums.length;
        boolean[] isUsed = new boolean[len];
        dfs(list,path,nums,len,isUsed,0);
        return list;
    }

    private void dfs(List<List<Integer>> list, Deque<Integer> path, int[] nums,int len, boolean[] isUsed, int depth) {
        if (len == depth){
            if (!list.contains(new ArrayList<>(path))){
                list.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = 0; i < len; i++) {
            //要求不能重复就用这个判断
//            if(isUsed[i] || (i>0 && !isUsed[i-1] && (nums[i] == nums[i-1]))){
//                continue;
//            }

            //如果可以重复
            if(isUsed[i]){
                continue;
            }

            path.addLast(nums[i]);
            isUsed[i] = true;
            dfs(list,path,nums,len,isUsed,depth+1);
            path.removeLast();
            isUsed[i] = false;
        }
    }
}
